package 力扣;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class 串联所有单词的子串 {
    public static void main(String[] args) {
        String s="barfoothefoobarman";
        String[] words={"foo","bar"};
        List<Integer> substring = findSubstring(s, words);
        System.out.println(substring.toString());
    }
    public static List<Integer> findSubstring(String s, String[] words) {
        ArrayList<Integer> list = new ArrayList<>();
        //单词的数量
        int wordsnum=words.length;
        //单词的长度
        int wordlen=words[0].length();
        //统计每个单词出现的数目
        HashMap<String, Integer> allwords = new HashMap<>();
        for (String word:words){
           allwords.put(word,allwords.getOrDefault(word,0)+1);
        }
        //如果字符数量小于数组字符的长度，则停止循环
        for (int i = 0; i < s.length()-wordsnum*wordlen+1; i++) {
            //新建一个字典，存储单词
            HashMap<String, Integer> map = new HashMap<>();
            //存储map中与allwords中单词相等的数量
            int count=0;
            while (count<wordsnum){
                String word=s.substring(i+count*wordlen,i+(count+1)*wordlen);
                //如果word等于words里的单词，添加进字典中
                if (allwords.containsKey(word)){
                        map.put(word,map.getOrDefault(word,0)+1);
                        if (map.get(word)>allwords.get(word))
                            break;
                }
                else{
                    break;
                }
                count++;
            }
            if (count==words.length){
                list.add(i);
            }
        }
        return list;
    }
}
